Approximate string search in spatial databases.
Abstract — This work presents a novel index structure, MHRtree, for efficiently answering approximate string match queries in large spatial databases. The MHR-tree is based on the R-tree augmented with the min-wise signature and the linear hashing technique. The min-wise signature for an index node u keeps a concise representation of the union of q-grams from strings under the sub-tree of u. We analyze the pruning functionality of such signatures based on set resemblance between the query string and the q-grams from the sub-trees of index nodes. MHR-tree supports a wide range of query predicates efficiently, including range and nearest neighbor queries. We also discuss how to estimate range query selectivity accurately. We present a novel adaptive algorithm for finding balanced partitions using both the spatial and string information stored in the tree. Extensive experiments on large real data sets demonstrate the efficiency and effectiveness of our approach. I.
Bed%2Dtree an all%2Dpurpose index structure for string similarity search based on edit distance.

Weighted Set%2DBased String Similarity.
Consider a universe of tokens, each of which is associated with a weight, and a database consisting of strings that can be represented as subsets of these tokens. Given a query string, also represented as a set of tokens, a weighted string similarity query identifies all strings in the database whose similarity to the query is larger than a user specified threshold. Weighted string similarity queries are useful in applications like data cleaning and integration for finding approximate matches in the presence of typographical mistakes, multiple formatting conventions, data transformation errors, etc. We show that this problem has semantic properties that can be exploited to design index structures that support very efficient algorithms for query answering. 1
On Multi%2DColumn Foreign Key Discovery.
A foreign/primary key relationship between relational tables is one of the most important constraints in a database. From a data analysis perspective, discovering foreign keys is a crucial step in understanding and working with the data. Nevertheless, more often than not, foreign key constraints are not specified in the data, for various reasons; e.g., some associations are not known to designers but are inherent in the data, while others become invalid due to data inconsistencies. This work proposes a robust algorithm for discovering single-column and multi-column foreign keys. Previous work concentrated mostly on discovering single-column foreign keys using a variety of rules, like inclusion dependencies, column names, and minimum/maximum values. We first propose a general rule, termed Randomness, that subsumes a variety of other rules. We then develop efficient approximation algorithms for evaluating randomness, using only two passes over the data. Finally, we validate our approach via extensive experiments using real and synthetic datasets. 1.
Methods for finding frequent items in data streams.

Type%2Dbased categorization of relational attributes.
In this work we concentrate on categorization of relational attributes based on their data type. Assuming that attribute type/characteristics are unknown or unidentifiable, we analyze and compare a variety of type-based signatures for classifying the attributes based on the semantic type of the data contained therein (e.g., router identifiers, social security numbers, email addresses). The signatures can subsequently be used for other applications as well, like clustering and index optimization/compression. This application is useful in cases where very large data collections that are generated in a distributed, ungoverned fashion end up having unknown, incomplete, inconsistent or very complex schemata and schema level meta-data. We concentrate on heuristically generating type-based attribute signatures based on both local and global computation approaches. We show experimentally that by decomposing data into q-grams and then considering signatures based on q-gram distributions, we achieve very good classification accuracy under the assumption that a large sample of the data is available for building the signatures. Then, we turn our attention to cases where a very small sample of the data is available, and hence accurately capturing the q-gram distribution of a given data type is almost impossible. We propose techniques based on dimensionality reduction and soft-clustering that exploit correlations between attributes to improve classification accuracy. 1.
Incremental maintenance of length normalized indexes for approximate string matching.
Approximate string matching is a problem that has received a lot of attention recently. Existing work on information retrieval has concentrated on a variety of similarity measures (TF/IDF, BM25, HMM, etc.) specifically tailored for document retrieval purposes. As new applications that depend on retrieving short strings are becoming popular (e.g., local search engines like YellowPages.com, Yahoo!Local, and Google Maps) new indexing methods are needed, tailored for short strings. For that purpose, a number of indexing techniques and related algorithms have been proposed based on length normalized similarity measures. A common denominator of indexes for length normalized measures is that maintaining the underlying structures in the presence of incremental updates is inefficient, mainly due to data dependent, precomputed weights associated with each distinct token and string. Incorporating updates usually is accomplished by rebuilding the indexes at regular time intervals. In this paper we present a framework that advocates lazy update propagation with the following key feature: Efficient, incremental updates that immediately reflect the new data in the indexes in a way that gives strict guarantees on the quality of subsequent query answers. More specifically, our techniques guarantee against false negatives and limit the number of false positives produced. We implement a fully working prototype and illustrate that the proposed ideas work really well in practice for real datasets.
Robust approximate aggregation in sensor data management systems.
In the emerging area of sensor-based systems, a significant challenge is to develop scalable, fault-tolerant methods to extract useful information from the data the sensors collect. An approach to this data management problem is the use of sensor database systems, which allow users to perform aggregation queries such as MIN, COUNT and AVG on the readings of a sensor network. In addition, more advanced queries such as frequency counting and quantile estimation can be supported. Due to energy limitations in sensor-based networks, centralized data collection is generally impractical, so most systems use in-network aggregation to reduce network traffic. However, even these aggregation strategies remain bandwidth-intensive when combined with the fault-tolerant, multi-path routing methods often used in these environments. To avoid this expense, we investigate the use of approximate in-network aggregation using small sketches. We present duplicate insensitive sketching techniques that can be implemented efficiently on small sensor devices with limited hardware support and we analyze both their performance and accuracy. Finally, we present an experimental evaluation that validates the effectiveness of our methods.


Finding the frequent items in streams of data.
doi:10.1145/1562764.1562789 The frequent items problem is to process a stream of items and find all those which occur more than a given fraction of the time. It is one of the most heavily studied problems in mining data streams, dating back to the 1980s. Many other applications rely directly or indirectly on finding the frequent items, and implementations are in use in large-scale industrial systems. In this paper, we describe the most important algorithms for this problem in a common framework. We place the different solutions in their historical context, and describe the connections between them, with the aim of clarifying some of the confusion that has surrounded their properties. To further illustrate the different properties of the algorithms, we provide baseline implementations. This allows us to give empirical evidence that there is considerable variation in the performance of frequent items algorithms. The best methods can be implemented to find frequent items with high accuracy using only tens of kilobytes of memory, at rates of millions of items per second on cheap modern hardware. 1.
Letter from the Special Issue Editor.
is published quarterly and is distributed to all TC members. Its scope includes the design, implementation, modelling, theory and application of database systems and their technology. Letters, conference information, and news should be
Efficient Approximate Search on String Collections.
This tutorial provides a comprehensive overview of recent research progress on the important problem of approximate search in string collections. We identify existing indexes, search algorithms, filtering strategies, selectivity-estimation techniques and other work, and comment on their respective merits and limitations. 1.
Repeatability %26 workability evaluation of SIGMOD 2009.

Fast Indexes and Algorithms for Set Similarity Selection Queries.
Abstract — Data collections often have inconsistencies that arise due to a variety of reasons, and it is desirable to be able to identify and resolve them efficiently. Set similarity queries are commonly used in data cleaning for matching similar data. In this work we concentrate on set similarity selection queries: Given a query set, retrieve all sets in a collection with similarity greater than some threshold. Various set similarity measures have been proposed in the past for data cleaning purposes. In this work we concentrate on weighted similarity functions like TF/IDF, and introduce variants that are well suited for set similarity selections in a relational database context. These variants have special semantic properties that can be exploited to design very efficient index structures and algorithms for answering queries efficiently. We present modifications of existing technologies to work for set similarity selection queries. We also introduce three novel algorithms based on the Threshold Algorithm, that exploit the semantic properties of the new similarity measures to achieve the best performance in theory and practice. I.
Randomized Synopses for Query Assurance on Data Streams.
Due to the overwhelming flow of information in many data stream applications, many companies may not be willing to acquire the necessary resources for deploying a Data Stream Management System (DSMS), choosing, alternatively, to outsource the data stream and the desired computations to a third-party. But data outsourcing and remote computations intrinsically raise issues of trust, making outsourced query assurance on data streams a problem with important practical implications. Consider a setting where a continuous “GROUP BY, SUM ” query is processed using a remote, untrusted server. A client with limited processing capabilities observing exactly the same stream as the server, registers the query on the server’s DSMS and receives results upon request. The client wants to verify the integrity of the results using significantly fewer resources than evaluating the query locally. Towards that goal, we propose a probabilistic verification algorithm for selection and aggregate/group-by queries, that uses constant space irrespective of the result-set size, has low update cost per stream element, and can have arbitrarily small probability of failure. We generalize this algorithm to allow some tolerance on the number of erroneous groups detected, in order to support semantic load shedding on the server. We also discuss the hardness of supporting random load shedding. Finally, we implement our techniques and perform an empirical evaluation using live network traffic. 1
Trip Planning Queries in Road Network Databases.

Trip Planning Queries in Road Network Databases.

Index Structures%2C Extensible.
To enable efficient similarity search in large databases, many indexing techniques use a linear transformation scheme to reduce dimensions and allow fast approximation. In this reduction approach the approximation is unbounded, so that the approximation volume extends across the dataspace. This causes over-estimation of retrieval sets and impairs performance. This paper presents a non-linear transformation scheme that extracts two important parameters specifying the data. We prove that these parameters correspond to a bounded volume around the search sphere, irrespective of dimensionality. We use a special workspace-mapping mechanism to derive tight bounds for the parameters and to prove further results, as well as highlighting insights into the problems and our proposed solutions. We formulate a measure that lower-bounds the Euclidean distance, and discuss the implementation of the technique upon a popular index structure. Extensive experiments confirm the superiority of this technique over recent state-of-the-art schemes. 1.
Indexing Spatio%2Dtemporal Archives.
Spatio-temporal objects — that is, objects that evolve over time — appear in many applications. Due to the nature of such applications, storing the evolution of objects through time in order to answer historical queries (queries that refer to past states of the evolution) requires a very large specialized database, what is termed in this article as a spatio-temporal archive. Efficient processing of historical queries on spatio-temporal archives requires equally sophisticated indexing schemes. Typical spatio-temporal indexing techniques represent the objects using minimum bounding regions (MBR) extended with a temporal dimension, which are then indexed using traditional multi-dimensional index structures. However, rough MBR approximations introduce excessive overlap between index nodes which deteriorates query performance. This article introduces a robust indexing scheme for answering spatio-temporal queries more efficiently. A number of algorithms and heuristics are elaborated, which can be used to preprocess a spatiotemporal archive in order to produce finer object approximations which, in combination with a multi-version index structure, will greatly improve query performance in comparison to the straightforward approaches. The proposed techniques introduce a query-efficiency vs. space tradeoff, that can help tune a structure according to available resources. Empirical observations for estimating the necessary amount of additional storage space required for improving query performance by a given factor are also provided. Moreover, heuristics for applying the proposed ideas in an online setting are discussed. Finally, a thorough experimental evaluation is conducted to show the merits of the proposed techniques.
R%2DTrees %2D A Dynamic Index Structure for Spatial Searching.

Hashed samples selectivity estimators for set similarity selection queries.
We study selectivity estimation techniques for set similarity queries. A wide variety of similarity measures for sets have been proposed in the past. In this work we concentrate on the class of weighted similarity measures (e.g., TF/IDF and BM25 cosine similarity and variants) and design selectivity estimators based on a priori constructed samples. First, we study the pitfalls associated with straightforward applications of random sampling, and argue that care needs to be taken in how the samples are constructed; uniform random sampling yields very low accuracy, while query sensitive realtime sampling is more expensive than exact solutions (both in CPU and I/O cost). We show how to build robust samples a priori, based on existing synopses for distinct value estimation. We prove the accuracy of our technique theoretically, and verify its performance experimentally. Our algorithm is orders of magnitude faster than exact solutions and has very small space overhead. 
Finding frequent items in data streams.
Abstract. We present a 1-pass algorithm for estimating the most frequent items in a data stream using very limited storage space. Our method relies on a novel data structure called a count sketch, which allows us to estimate the frequencies of all the items in the stream. Our algorithm achieves better space bounds than the previous best known algorithms for this problem for many natural distributions on the item frequencies. In addition, our algorithm leads directly to a 2-pass algorithm for the problem of estimating the items with the largest (absolute) change in frequency between two data streams. To our knowledge, this problem has not been previously studied in the literature. 1
Norm
This paper will propose an objective measure based on the information theoretic notion of mutual  information, for estimating word association norms from computer readable corpora. (The standard method  of obtaining word association norms, testing a few thousand subjects on a few hundred words, is both costly  and unreliable.) The proposed measure, the association ratio, estimates word association norms directly  from computer readable corpora, making it possible to estimate norms for tens of thousands of words
Continuous Constraint Query Evaluation for Spatiotemporal Streams.
Abstract. In this paper we study the evaluation of continuous constraint queries (CCQs) for spatiotemporal streams. A CCQ triggers an alert whenever a configuration of constraints between streaming events in space and time are satisfied. Consider, for instance, a server that receives updates from GPS-enabled agents that report their positions and other measurements (e.g., environmental readings). An example of CCQ is: “Alert whenever at least 5 readings closer than 5km to each other and within a time difference of 5 minutes report high pressures and low temperatures”. We model CCQs as Constraint Satisfaction Problems (CSPs) and develop solutions for their continuous evaluation. Our techniques (1) consider the fast arrival rate of incoming events, and (2) minimize the memory requirements, without using predefined window constraints, but by utilizing the structure of the queries. In order to show the merits of the proposed techniques, we implement a system prototype and evaluate it with real data. 1
Proof%2DInfused Streams Enabling Authentication of Sliding Window Queries On Streams.

Query%2Dsensitive embeddings.
A common problem in many types of databases is retrieving the most similar matches to a query object. Finding those matches in a large database can be too slow to be practical, especially in domains where objects are compared using computationally expensive similarity (or distance) measures. This paper proposes a novel method for approximate nearest neighbor retrieval in such spaces. Our method is embedding-based, meaning that it constructs a function that maps objects into a real vector space. The mapping preserves a large amount of the proximity structure of the original space, and it can be used to rapidly obtain a short list of likely matches to the query. The main novelty of our method is that it constructs, together with the embedding, a query-sensitive distance measure that should be used when measuring distances in the vector space. The term &#034;querysensitive &#034; means that the distance measure changes depending on the current query object. We report experiments with an image database of handwritten digits, and a time-series database. In both cases, the proposed method outperforms existing state-of-the-art embedding methods, meaning that it provides significantly better trade-o#s between e#ciency and retrieval accuracy.

Random Sampling for Continuous Streams with Arbitrary Updates.


Global distance%2Dbased segmentation of trajectories.
This work introduces distance-based criteria for segmentation of object trajectories. Segmentation leads to simplification of the original objects into smaller, less complex primitives that are better suited for storage and retrieval purposes. Previous work on trajectory segmentation attacked the problem locally, segmenting separately each trajectory of the database. Therefore, they did not directly optimize the inter-object separability, which is necessary for mining operations such as searching, clustering, and classification on large databases. In this paper we analyze the trajectory segmentation problem from a global perspective, utilizing data aware distance-based optimization techniques, which optimize pairwise distance estimates hence leading to more efficient object pruning. We first derive exact solutions of the distance-based formulation. Due to the intractable complexity of the exact solution, we present an approximate, greedy solution that exploits forward searching of locally optimal solutions. Since the greedy solution also imposes a prohibitive computational cost, we also put forward more lightweight variance-based segmentation techniques, which intelligently “relax ” the pairwise distance only in the areas that affect the least the mining operations.
Indexing spatiotemporal archives.

Dynamic authenticated index structures for outsourced databases.
Abstract. In an outsourced database (ODB) system the database owner publishes data through a number of remote servers, with the goal of enabling clients at the edge of the network to access and query the data more efficiently. As servers might be untrusted or can be compromised, query authentication becomes an essential component of ODB systems. In this chapter we present three techniques to authenticate selection range queries and we analyze their performance over different cost metrics. In addition, we discuss extensions to other query types. 1
Indexing Multidimensional Time%2DSeries.

Indexing spatiotemporal archives.

Time relaxed spatiotemporal trajectory joins.

Efficient trajectory joins using symbolic representations.

RPJ Producing Fast Join Results on Streams through Rate%2Dbased Optimization.


Conceptual Partitioning An Efficient Method for Continuous Nearest Neighbor Monitoring.
Given a set of objects P and a query point q, a k nearest neighbor (k-NN) query retrieves the k objects in P that lie closest to q. Even though the problem is well-studied for static datasets, the traditional methods do not extend to highly dynamic environments where multiple continuous queries require real-time results, and both objects and queries receive frequent location updates. In this paper we propose conceptual partitioning (CPM), a comprehensive technique for the efficient monitoring of continuous NN queries. CPM achieves low running time by handling location updates only from objects that fall in the vicinity of some query (and ignoring the rest). It can be used with multiple, static or moving queries, and it does not make any assumptions about the object moving patterns. We analyze the performance of CPM and show that it outperforms the current state-of-the-art algorithms for all problem settings. Finally, we extend our framework to aggregate NN (ANN) queries, which monitor the data objects that minimize the aggregate distance with respect to a set of query points (e.g., the objects with the minimum sum of distances to all query points). 1.

On Trip Planning Queries in Spatial Databases.
In this paper we discuss a new type of query in Spatial Databases, called the Trip Planning Query (TPQ). Given a set of points of interest P in space, where each point belongs to a specific category, a starting point S and a destination E, TPQ retrieves the best trip that starts at S, passes through at least one point from each category, and ends at E. For example, a driver traveling from Boston to Providence might want to stop to a gas station, a bank and a post office on his way, and the goal is to provide him with the best possible route (in terms of distance, traffic, road conditions, etc.). The difficulty of this query lies in the existence of multiple choices per category. In this paper, we study fast approximation algorithms for TPQ in a metric space. We provide a number of approximation algorithms with approximation ratios that depend on either the number of categories, the maximum number of points
Complex Spatio%2DTemporal Pattern Queries.
This paper introduces a novel type of query, what we name Spatio-temporal Pattern Queries (STP). Such a query specifies a spatio-temporal pattern as a sequence of distinct spatial predicates where the predicate temporal ordering (exact or relative) matters. STP queries can use various types of spatial predicates (range search, nearest neighbor, etc.) where each such predicate is associated (1) with an exact temporal constraint (a time-instant or a time-interval), or (2) more generally, with a relative order among the other query predicates. Using traditional spatio-temporal index structures for these types of queries would be either inefficient or not an applicable solution. Alternatively, we propose specialized query evaluation algorithms for STP queries With Time. We also present a novel index structure, suitable for STP queries With Order. Finally, we conduct a comprehensive experimental evaluation to show the merits of our techniques. 1
Indexing Multi%2DDimensional Trajectories for Similarity Queries.


SaIL A Spatial Index Library for Efficient Application Integration.


Mining%2C indexing%2C and querying historical spatiotemporal data.
Abstract—Given a large spatio-temporal database of events, where each event consists of the fields event ID, time, location, and event type, mining spatio-temporal sequential patterns identifies significant event-type sequences. Such spatio-temporal sequential patterns are crucial to the investigation of spatial and temporal evolutions of phenomena in many application domains. Recent research literature has explored the sequential patterns on transaction data and trajectory analysis on moving objects. However, these methods cannot be directly applied to mining sequential patterns from a large number of spatio-temporal events. Two major research challenges still remain: 1) the definition of significance measures for spatio-temporal sequential patterns to avoid spurious ones and 2) the algorithmic design under the significance measures, which may not guarantee the downward closure property. In this paper, we propose a sequence index as the significance measure for spatio-temporal sequential patterns, which is meaningful due to its interpretability using spatial statistics. We propose a novel algorithm called Slicing-STS-Miner to tackle the algorithmic design challenge using the spatial sequence index, which does not preserve the downward closure property. We compare the proposed algorithm with a simple algorithm called STS-Miner that utilizes the weak monotone property of the sequence index. Performance evaluations using both synthetic and real-world data sets show that the Slicing-STS-Miner is an order of magnitude faster than STS-Miner for large data sets. Index Terms—Spatio-temporal sequential pattern, density ratio, sequence index, slicing, performance. Ç 1
Spatio%2DTemporal Data Services in a Shared%2DNothing Environment.


SaIL A Library for Efficient Application Integration of Spatial Indices.
Many scientific applications deal with spatial, spatiotemporal and other multidimensional indexing structures, typically managing millions of objects with arbitrary and complex features. Choosing the appropriate method to index such data becomes rather difficult. Having an index library that can combine different indices under the same programming interface is thus very valuable. In this paper we present SaIL (SpAtial Index Library), a robust and extensible library that enables simple integration of spatial index structures in existing applications. We mainly focus on design issues and elaborate on techniques for making the framework generic enough, so that it can support user defined data types, customizable spatial queries, and a broad range of spatial (and spatio-temporal) index structures. The library is publicly available and has already been successfully utilized for research and commercial applications.

Performance Evaluation of Spatio%2Dtemporal Selectivity Estimation Techniques.
Abstract — Many novel spatio-temporal applications deal with moving objects. In such environments, a database typically maintains the initial position and the moving function for each object. Instead of updating the database whenever an object position changes (which is not manageable), updates are issued whenever the moving function deviates beyond a given threshold. For simplicity, we assume that objects move with linear trajectories. Maintaining the moving functions in a database introduces novel problems. For example, the database can answer queries about object positions in the future: “find all objects that will be in area A, 10 minutes from now”. In this paper we present a thorough performance evaluation of techniques for estimating the selectivity of such queries. We consider various existing estimators that can be stored in main memory and are updated dynamically. Furthermore, we propose two new approaches, a technique that uses histograms and a secondary index based estimator. We run a diverse set of experiments to identify the strengths and weaknesses of every approach, using a wide variety of datasets. I.
On%2DLine Discovery of Dense Areas in Spatio%2Dtemporal Databases.
Abstract — Moving object databases have received considerable attention recently. Previous work has concentrated mainly on modeling and indexing problems, as well as query selectivity estimation. Here we introduce a novel problem, that of addressing density-based queries in the spatio-temporal domain. For example: “Find all regions that will contain more than 500 objects, ten minutes from now”. The user may also be interested in finding the time period (interval) that the query answer remains valid. We formally define a new class of density-based queries and give approximate, on-line techniques that answer them efficiently. Typically the threshold above which a region is considered to be dense is part of the query. The difficulty of the problem lies in the fact that the spatial and temporal predicates are not specified by the query. The techniques we introduce find all candidate dense regions at any time in the future. To make them more scalable we subdivide the spatial universe using a grid and limit queries within a pre-specified time horizon. Finally, we validate our approaches with a thorough experimental evaluation. I.
Efficient Indexing of Spatiotemporal Objects.
Spatiotemporal objects, i.e., objects which change their position and/or extent over time appear in many  applications. In this paper we examine the problem of indexing large volumes of such data. Important in  this environment is how the spatiotemporal objects move and/or change. We consider a rather general case  where object movements/changes are defined by combinations of polynomial functions. We further concentrate  on &#034;snapshot&#034; as well as small &#034;interval&#034; queries as these are quite common when examining the history of  the gathered data. The obvious approach that approximates each spatiotemporal object by an MBR and uses  a traditional multidimensional access method to index them is inefficient. Objects that &#034;live&#034; for long time  intervals have large MBRs which introduce a lot of empty space. Clustering long intervals has been dealt in  temporal databases by the use of partially persistent indices. What differentiates this problem from traditional  temporal indexing, is that objects are allowed to move/change during their lifetime. Better ways are thus needed  to approximate general spatiotemporal objects. One obvious solution is to introduce artificial splits: the lifetime  of a long-lived object is split into smaller consecutive pieces. This decreases the empty space but increases the  number of indexed MBRs. We first give an optimal algorithm and a heuristic for splitting a given spatiotemporal  object in a predefined number of pieces. Then, given an upper bound on the total number of possible splits,  we present three algorithms that decide how the splits are distributed among all the objects so that the total  empty space is minimized. The number of splits cannot be increased indefinitely since the extra objects will  eventually affect query performance. Usi...
Indexing Animated Objects Using Spatiotemporal Access Methods.
AbstractÐWe present a new approach for indexing animated objects and efficiently answering queries about their position in time and space. In particular, we consider an animated movie as a spatiotemporal evolution. A movie is viewed as an ordered sequence of frames, where each frame is a 2D space occupied by the objects that appear in that frame. The queries of interest are range queries of the form, ªfind the objects that appear in area S between frames fi and fjº as well as nearest neighbor queries such as, ªfind the q nearest objects to a given position A between frames fi and fj.º The straightforward approach to index such objects considers the frame sequence as another dimension and uses a 3D access method (such as, an R-Tree or its variants). This, however, assigns long ªlifetimeº intervals to objects that appear through many consecutive frames. Long intervals are difficult to cluster efficiently in a 3D index. Instead, we propose to reduce the problem to a partial-persistence problem. Namely, we use a 2D access method that is made partially persistent. We show that this approach leads to faster query performance while still using storage proportional to the total number of changes in the frame evolution. What differentiates this problem from traditional temporal indexing approaches is that objects are allowed to move and/or change their extent continuously between frames. We present novel methods to approximate such object evolutions. We formulate an optimization problem for which we provide an optimal solution for the case where objects move linearly. Finally, we present an extensive experimental study of the proposed methods. While we concentrate on animated movies, our approach is general and can be applied to other spatiotemporal applications as well. Index TermsÐAccess methods, spatiotemporal databases, animated objects, multimedia. 1
